package org.lex.collection;

import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;

public abstract class Heap<E> extends AbstractCollection<E> implements Collection<E> {
	protected static final int INIT_SIZE = 8;
	protected static final Object[] EMPTY = new Object[0];

	protected Comparator<? super E> comparator = null;
	private int size = 0;
	private Object[] data = EMPTY;

	public Heap() {
		this.size = 0;
		this.data = EMPTY;
	}

	public Heap(Collection<E> c) {
		int minCapacity = c.size();
		this.ensureCapacity(minCapacity);
		this.size = minCapacity;
		int i = 0;
		for (E e : c) {
			this.data[i++] = e;
		}
		this.buildHeap();
	}

	// ========== org.lex.collection.Heap ==========
	protected abstract void buildHeap();

	protected abstract void heapifyDown(int index);

	protected abstract void heapifyUp(int index);

	protected abstract boolean isHeap();

	public void trimToSize() {
		int properCapacity = getProperCapacity(this.size);
		if (properCapacity < this.size) {
			Object[] newData = new Object[properCapacity];
			System.arraycopy(data, 0, newData, 0, this.size);
			this.data = newData;
		}
	}

	public void ensureCapacity(int minCapacity) {
		if (this.data.length < minCapacity) {
			Object[] newData = new Object[getProperCapacity(minCapacity)];
			System.arraycopy(data, 0, newData, 0, Math.min(this.data.length, this.size));
			this.data = newData;
		}
	}

	private static int getProperCapacity(int minCapacity) {
		int newCapacity = INIT_SIZE;
		while (newCapacity < minCapacity) {
			newCapacity <<= 1;
		}
		return newCapacity;
	}

	protected E get(int index) {
		return (E) data[index];
	}

	protected int indexOf(Object o) {
		if (null != o) {
			for (int i = 0; i < size; i++) {
				if (o == data[i] || o.equals(data[i])) {
					return i;
				}
			}
		}
		return -1;
	}

	protected int getParent(int index) {
		return (index - 1) >> 1;
	}

	protected int getLeftChild(int index) {
		return (index << 1) + 1;
	}

	protected int getRightChild(int index) {
		return (index + 1) << 1;
	}

	protected int getFirstLeaf() {
		return size >>> 1;
	}

	protected int getLastBranch() {
		return this.getFirstLeaf() - 1;
	}

	protected void swap(int a, int b) {
		Object tmp = data[a];
		data[a] = data[b];
		data[b] = tmp;
	}

	protected int compare(E a, E b) {
		if (null != comparator) {
			return comparator.compare(a, b);
		} else {
			return ((Comparable<E>) a).compareTo(b);
		}
	}

	public String toString() {
		StringBuilder buf = new StringBuilder();
		buf.append('[');
		for (int i = 0; i < size; i++) {
			buf.append(this.data[i]);
			if (i < size - 1) {
				buf.append(", ");
			}
		}
		buf.append("]#").append(this.size);
		return buf.toString();
	}

	public String toTree() {
		String nl = System.getProperty("line.separator", "\n");
		StringBuilder buf = new StringBuilder();
		buf.append(this.toString()).append(" is heap? ").append(this.isHeap()).append(nl);

		int firstLeaf = this.getFirstLeaf();
		buf.append(firstLeaf).append(" branches:").append(nl);
		for (int i = 0; i < firstLeaf; i++) {
			int parent = i;
			buf.append('[').append(this.data[parent]).append(": ");
			int left = this.getLeftChild(parent);
			if (left < this.size) {
				buf.append(this.data[left]);

				int right = this.getRightChild(parent);
				if (right < this.size) {
					buf.append(", ").append(this.data[right]);
				}
			}
			buf.append(']').append(nl);
		}

		return buf.toString();
	}

	// ========== java.util.Collection ==========
	@Override
	public boolean add(E e) {
		int insertIndex = this.size;
		this.ensureCapacity(++this.size);
		this.data[insertIndex] = e;
		this.heapifyUp(insertIndex);
		return true;
	}

	@Override
	public void clear() {
		this.size = 0;
		Arrays.fill(data, null);
	}

	@Override
	public boolean contains(Object o) {
		return this.indexOf(o) >= 0;
	}

	@Override
	public boolean isEmpty() {
		return 0 == size;
	}

	@Override
	public Iterator<E> iterator() {
		return new HeapIterator<E>(data, size);
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object[] toArray() {
		return Arrays.copyOf(data, size);
	}

	@Override
	public <T> T[] toArray(T[] a) {
		if (a.length < size) {
			return (T[]) Arrays.copyOf(data, size, a.getClass());
		} else {
			System.arraycopy(data, 0, a, 0, size);
			return a;
		}
	}

	private static final class HeapIterator<T> implements Iterator<T> {
		private final Object[] data;
		private final int size;
		private int position = 0;

		public HeapIterator(Object[] data, int size) {
			this.data = data;
			this.size = size;
		}

		@Override
		public boolean hasNext() {
			return position < size;
		}

		@Override
		public T next() {
			return (T) data[position++];
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}
}
